\documentclass[a4paper]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{charter}   % tipografia
\usepackage{graphicx}
%\usepackage{makeidx}

%\usepackage{float}
%\usepackage{amsmath, amsthm, amssymb}
%\usepackage{amsfonts}
%\usepackage{sectsty}
%\usepackage{charter}
%\usepackage{wrapfig}
%\usepackage{listings}
%\lstset{language=C}


\input{codesnippet}
\input{page.layout}
% \setcounter{secnumdepth}{2}
\usepackage{underscore}
\usepackage{caratula}
\usepackage{url}


% ******************************************************** %
%              TEMPLATE DE INFORME ORGA2 v0.1              %
% ******************************************************** %
% ******************************************************** %
%                                                          %
% ALGUNOS PAQUETES REQUERIDOS (EN UBUNTU):                 %
% ========================================
%                                                          %
% texlive-latex-base                                       %
% texlive-latex-recommended                                %
% texlive-fonts-recommended                                %
% texlive-latex-extra?                                     %
% texlive-lang-spanish (en ubuntu 13.10)                   %
% ******************************************************** %



\begin{document}


\thispagestyle{empty}
\materia{Organización del Computador II}
\submateria{Primer Cuatrimestre de 2014}
\titulo{Trabajo Práctico II}
\subtitulo{subtitulo del trabajo}
\integrante{Nombre}{XXX/XX}{mail}
\integrante{Nombre}{XXX/XX}{mail}

\maketitle
\newpage

\thispagestyle{empty}
\vfill
\begin{abstract}
En el presente trabajo se describe la problemática de ...
\end{abstract}

\thispagestyle{empty}
\vspace{3cm}
\tableofcontents
\newpage


%\normalsize
\newpage

\section{Objetivos generales}

El objetivo de este Trabajo Práctico es analizar las ventajas y desventajas del modelo de programación SIMD. Para ello se implementaron cuatro filtros para 
procesamiento de imágenes en dos versiones: la primera en lenguaje C y la segunda en lenguaje ensamblador, haciendo uso de las instrucciones SSE que provee la arquitectura Intel para procesamiento 
simultáneo de datos. Luego se testearon para garantizar que, para cada filtro, con ambas versiones se obtuvieran los mismos resultados
en cuanto al efecto generado en las imágenes.

Finalizada la etapa de testeo, 
\section{Contexto}

Por lo que entiendo, habría que escribir que las imágenes son vectores de pixeles, donde los pixeles son structs de 3 bytes.
También mencionar que usamos opencv.
\subsection{Filtro Tiles}
Este filtro se aplica pixel a pixel en una imagen. Dados cuatro parámetros de tipo entero, se selecciona una porción rectangular ({\textit tile}) de la imagen, y se escribe ese rectángulo
repetidamente en toda la imagen destino. Los parámetros mencionados son el ancho y alto del {\textit tile}, y el desplazamiento del mismo en los ejes x e y.
 
A continuación describiremos las diferencias de implementación de las versiones del filtro, por lo que es importante tener en cuenta las siguientes variables:
\begin{itemize}
 \item src: Imagen fuente, considerada como matriz de píxeles.
 \item dst: Imagen destino, considerada como matriz de píxeles.
 \item tamx: ancho de tile.
 \item tamy: alto de tile.
 \item offsetx: desplazamiento de tile en el eje x.
 \item offsety: desplazamiento de tile en el eje y.
 \item i: índice de fila de la imagen.
 \item j: índice de columna de la imagen.
 \item $i_t$: índice de fila de tile (para versión Assembler).
 \item $j_t$: índice de columna de tile (para versión Assembler).
\end{itemize}

\subsubsection{Versión implementada en C}
La implementación en C consta de dos ciclos anidados con los cuales recorremos la imagen de a un pixel por vez. En el cuerpo del ciclo no se aplican operaciones a los datos, solamente se copiamos en el pixel $dst_{ij}$ el pixel $src_{[(i\ mod\ tamy) + offsety][(j*3\ mod\ tamx*3) + 3*offsetx]}$.
Las variables $j$, $tamx$ y $offsetx$ se multiplican por tres porque estas variables se refieren a columnas de la imagen, y lo que necesitábamos era hacer una copia byte a byte.
\subsubsection{Versión implementada en ASM}
A diferencia de la implementación en C, aquí utilizamos un ciclo principal ({\textit .col}). Cabe aclarar que para un correcto funcionamiento del filtro en Assembler, en el código multiplicamos las variables referidas al ancho de la imagen y tile por tres, antes de iniciar el ciclo principal.
En cada iteración de .col, copiamos en el registro multimedia XMM0 16 bytes de $src$.
Luego copiamos en $dst$ esos 16 bytes. Luego se incrementan los índices $j$ y $j_t$ en 15 y no en 16. Esto es para reducir la cantidad de situaciones posibles en las que la distancia entre
el fin de fila y el índice j sea menor a 16. Antes de reiniciar el ciclo, el código chequea que la distancia al fin de la fila del tile a copiar ($tamx - j_t$) sea mayor a 16, en cuyo caso continúa con la próxima iteración. Caso contrario salta a una subrutina en la que o bien reinicia el valor de $j_t$, para comenzar la inserción en $dst$ de una 
fila de otra réplica del tile, o bien se retroceden las variables necesarias para que en la próxima iteración
se copien 16 bytes sin exceder el borde del tile. Como asumimos que tamx*3 es mayor a 48, sabemos que en el peor caso se llama a esta subrutina una vez cada tres iteraciones de {\textit .col}.
Posteriormente en el mismo ciclo, el código chequea que $fin\ de\ fila - j$ sea mayor a 16. Esto es necesario porque en el caso que la imagen tenga un ancho que no sea múltiplo de 16, las funciones de OpenCV agregan lo que se denomina padding, lo cual es un grupo de bytes que sirven para alcanzar ese tamaño de filas. No deben ser procesados 
ni copiados por el programa del filtro, ya que no contienen información de la imagen. Como en la comparación anterior, se continúa con una subrutina si estamos cerca del padding. Si el índice $j$ está en el fin de fila la subrutina llama a otra subrutina que modifica las variables para posibilitar el procesamiento de la siguiente fila de la imagen.
Si no, se decrementan las variables para que en la próxima iteración de .col se copien los últimos 16 bytes de la fila. Como las imágenes con las que trabajamos tienem un ancho de fila mayor a 120 píxeles (360 bytes), en el peor caso se llama a la subrutina mencionada una vez cada veinticuatro iteraciones.
Entonces, como las variables $j$ y $j_t$ se utilizan en cada iteración, mientras que las variables $i$ e $i_t$ se utilizan con menos frecuencia, y debido a la escasez de registros de propósito general, se ubicaron $j$ y $j_t$ en R10 y R11 respectivamente, mientras que $i$ e $i_t$ se ubicaron en la pila.
\begin{figure}
  \begin{center}
	\includegraphics[scale=0.66]{imagenes/logouba.jpg}
	\caption{Descripcion de la figura}
	\label{nombreparareferenciar}
  \end{center}
\end{figure}


\paragraph{\textbf{Titulo del parrafo} } Bla bla bla bla.
Esto se muestra en la figura~\ref{nombreparareferenciar}.



\begin{codesnippet}
\begin{verbatim}

struct Pepe {

    ...

};

\end{verbatim}
\end{codesnippet}



\section{Desarrollo}
En esta sección describimos para cada filtro, su funcionalidad e implementación en ambas versiones (C y Ensamblador), además de los experimentos realizados
para medir la performance de los mismos. Finalmente analizamos los resultados obtenidos.
\subsection{Diferencias estructurales entre los códigos de desensamblado de la versión C con diferentes optimizaciones}
Al compilar el filtro {\textit tiles} programado en C, el compilador GCC genera un código en lenguaje ensamblador, el cual se puede leer utilizando el comando {\textit objdump}. Dependiendo de la opción de optimización 
utilizada en dicha compilación, este código variará estructuralmente, y como consecuencia variará su tiempo de ejecución. En esta sección analizaremos las diferencias estructurales entre el código genereado por el compilador sin optimización alguna, y el código obtenido con la optimización O1.
El siguiente es un extracto del código assembly del filtro {\textit tiles} sin optimización.
\begin{codesnippet}
\begin{verbatim}
Disassembly of section .text:

0000000000000000 <tiles_c>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 89 7d b8          	mov    %rdi,-0x48(%rbp)
   8:	48 89 75 b0          	mov    %rsi,-0x50(%rbp)
   c:	89 55 ac             	mov    %edx,-0x54(%rbp)
   f:	89 4d a8             	mov    %ecx,-0x58(%rbp)
  12:	44 89 45 a4          	mov    %r8d,-0x5c(%rbp)
  16:	44 89 4d a0          	mov    %r9d,-0x60(%rbp)
  1a:	8b 4d a4             	mov    -0x5c(%rbp),%ecx
  1d:	48 63 c1             	movslq %ecx,%rax
  20:	48 83 e8 01          	sub    $0x1,%rax
  24:	48 89 45 c8          	mov    %rax,-0x38(%rbp)
  28:	48 8b 45 b8          	mov    -0x48(%rbp),%rax
  2c:	48 89 45 d0          	mov    %rax,-0x30(%rbp)
  30:	8b 75 a0             	mov    -0x60(%rbp),%esi
  33:	48 63 c6             	movslq %esi,%rax
  36:	48 83 e8 01          	sub    $0x1,%rax
  3a:	48 89 45 d8          	mov    %rax,-0x28(%rbp)
  3e:	48 8b 45 b0          	mov    -0x50(%rbp),%rax
  42:	48 89 45 e0          	mov    %rax,-0x20(%rbp)
  46:	c7 45 f8 00 00 00 00 	movl   $0x0,-0x8(%rbp)
  4d:	e9 cb 00 00 00       	jmpq   11d <tiles_c+0x11d>
\end{verbatim}
\end{codesnippet}
Se observa que el compilador reserva un espacio en la pila para guardar allí tanto las variables locales como las recibidas como parámetros. Tener todos los datos en la pila implica que el programa accederá a memoria 
muchas veces por ciclo. En el próximo fragmento se puede apreciar como se transfieren los datos. A pesar de que la arquitectura Intel provee dieciseis registros de próposito 
general, aquí el código parece usar la mínima cantidad de ellos, limitándose al uso de los registros rax, rcx, rdx, y rsi y rdi en menor medida. Esto trae como consecuencia una excesiva cantidad de instruciones empleadas en el movimiento de datos.
\begin{codesnippet}
\begin{verbatim}
  5e:	8b 45 f8             	mov    -0x8(%rbp),%eax
  61:	48 63 d0             	movslq %eax,%rdx
  64:	48 63 c6             	movslq %esi,%rax
  67:	48 89 d7             	mov    %rdx,%rdi
  6a:	48 0f af f8          	imul   %rax,%rdi
  6e:	8b 55 fc             	mov    -0x4(%rbp),%edx
  71:	89 d0                	mov    %edx,%eax
  73:	01 c0                	add    %eax,%eax
  75:	01 d0                	add    %edx,%eax
  77:	48 98                	cltq   
  79:	48 01 f8             	add    %rdi,%rax
  7c:	48 03 45 e0          	add    -0x20(%rbp),%rax
  80:	48 89 45 e8          	mov    %rax,-0x18(%rbp)
  84:	8b 45 f8             	mov    -0x8(%rbp),%eax
  87:	89 c2                	mov    %eax,%edx
  89:	c1 fa 1f             	sar    $0x1f,%edx
  8c:	f7 7d 18             	idivl  0x18(%rbp)
  8f:	89 d0                	mov    %edx,%eax
  91:	03 45 28             	add    0x28(%rbp),%eax
  94:	48 63 d0             	movslq %eax,%rdx
  97:	48 63 c1             	movslq %ecx,%rax
  9a:	48 89 d7             	mov    %rdx,%rdi
  9d:	48 0f af f8          	imul   %rax,%rdi
  a1:	8b 55 fc             	mov    -0x4(%rbp),%edx
  a4:	89 d0                	mov    %edx,%eax
  a6:	01 c0                	add    %eax,%eax
  a8:	44 8d 04 10          	lea    (%rax,%rdx,1),%r8d
  ac:	8b 55 10             	mov    0x10(%rbp),%edx

\end{verbatim}
\end{codesnippet}
Ahora analizaremos como las características del código generado con la optimización O1.
\begin{codesnippet}
\begin{verbatim}
Disassembly of section .text:

0000000000000000 <tiles_c>:
   0:	41 57                	push   %r15
   2:	41 56                	push   %r14
   4:	41 55                	push   %r13
   6:	41 54                	push   %r12
   8:	55                   	push   %rbp
   9:	53                   	push   %rbx
   a:	41 89 d2             	mov    %edx,%r10d
   d:	41 89 ce             	mov    %ecx,%r14d
  10:	44 8b 5c 24 38       	mov    0x38(%rsp),%r11d
  15:	44 8b 64 24 48       	mov    0x48(%rsp),%r12d
  1a:	85 c9                	test   %ecx,%ecx
  1c:	0f 8e 95 00 00 00    	jle    b7 <tiles_c+0xb7>
\end{verbatim}
\end{codesnippet}
A diferencia del código anterior, en este no sólo se aprovecha que los parámetros se obtienen en registros de propósito general, sino que las variables locales también 
se guardan en ellos. De esta forma se deben computar menos instrucciones en la parte inicial del programa, previo a ingresar al ciclo. En cuanto al modo de transferencia de datos, 
en el siguiente fragmento se observa que también se utilizan los registros rax, rcx, rdx, pero al no utilizar la pila, se computa una pequeña cantidad de instrucciones para el acceso a memoria, obteniéndose un código más corto.
\begin{codesnippet}
\begin{verbatim}
  22:	47 8d 1c 5b          	lea    (%r11,%r11,2),%r11d
  26:	47 8d 24 64          	lea    (%r12,%r12,2),%r12d
  2a:	4d 63 f9             	movslq %r9d,%r15
  2d:	41 b9 00 00 00 00    	mov    $0x0,%r9d
  33:	41 bd 00 00 00 00    	mov    $0x0,%r13d
  39:	4d 63 c0             	movslq %r8d,%r8
  3c:	4c 89 44 24 f8       	mov    %r8,-0x8(%rsp)
  41:	43 8d 2c 52          	lea    (%r10,%r10,2),%ebp
  45:	eb 48                	jmp    8f <tiles_c+0x8f>
  47:	4c 63 c1             	movslq %ecx,%r8
  4a:	4d 01 c8             	add    %r9,%r8
  4d:	49 01 f0             	add    %rsi,%r8
  50:	89 c8                	mov    %ecx,%eax
  52:	89 ca                	mov    %ecx,%edx
  54:	c1 fa 1f             	sar    $0x1f,%edx
  57:	41 f7 fb             	idiv   %r11d
  5a:	44 01 e2             	add    %r12d,%edx
  5d:	48 63 d2             	movslq %edx,%rdx
  60:	48 01 da             	add    %rbx,%rdx
  63:	48 01 fa             	add    %rdi,%rdx
  66:	0f b6 02             	movzbl (%rdx),%eax
  69:	41 88 00             	mov    %al,(%r8)
  6c:	0f b6 42 01          	movzbl 0x1(%rdx),%eax
  70:	41 88 40 01          	mov    %al,0x1(%r8)
  74:	0f b6 42 02          	movzbl 0x2(%rdx),%eax
  78:	41 88 40 02          	mov    %al,0x2(%r8)
  7c:	83 c1 03             	add    $0x3,%ecx
  7f:	39 e9                	cmp    %ebp,%ecx
  81:	75 c4                	jne    47 <tiles_c+0x47>
\end{verbatim}
\end{codesnippet}
\subsection{Diferencias en performance entre las versiones en ASM y en C con diferentes optimizaciones}
Las instrucciones SSE permiten procesar y realizar movimientos de memoria a los registros de más de un dato por vez. Entonces, basándonos en esta cualidad, creemos que los filtros programados con dichas instrucciones
tendrán una mayor performance que las versiones en C. Por otro lado, como se mencionó en la sección anterior, el compilador GCC provee optimizaciones para el código de desensamblado. También en este caso nuestra hipótesis es que la performance de las versiones en ASM
superarán a las de las versiones en C con alguna de las optimizaciones O1, O2 u O3. A fin de poder verificar nuestras hipótesis, medimos el tiempo en ciclos de máquina que demandan los filtros en las siguientes versiones:
\begin{itemize}
 \item Versión en ASM, utilizando instrucciones SSE
 \item En C
 \item En C compilado con O1
 \item En C compilado con O2
 \item En C compilado con O3
\end{itemize}
Para realizar las mediciones debimos realizar modificaciones en la siquiente función, 
la cual es la que llama el archivo {\textit tp2} para ejecutar el filtro pasado por parámetro:
\begin{codesnippet}
\begin{verbatim}
void correr_filtro_imagen(configuracion_t *config, aplicador_fn_t aplicador)
{
	unsigned long int start = 0;
	unsigned long int end = 0;

	snprintf(config->archivo_salida, sizeof(config->archivo_salida), "%s/%s.%s.%s%s.bmp",
                 config->carpeta_salida, basename(config->archivo_entrada), 
                 config->nombre_filtro, C_ASM(config), config->extra_archivo_salida );
	
	if (config->nombre)
	{
		printf("%s\n", basename(config->archivo_salida));
	}
	else
	{
			opencv_abrir_imagenes(config);
			aplicador(config);
			opencv_liberar_imagenes(config);
	}
}
\end{verbatim}
\end{codesnippet}
Donde aplicador(config) es la función que ejecuta el filtro.
La arquitectura Intel provee la instrucción {\textit rdtsc}, que devuelve la cantidad de ciclos de máquina empleados hasta el momento de la llamada a dicha instrucción.
Utilizando la macro MEDIR_TIEMPO_START provista por la cátedra, la cual utiliza la instrucción rdtsc, modificamos el cuerpo de {\textit else} de la función anterior.
\begin{codesnippet}
\begin{verbatim}
else{
        for(int i = 0; i < 100; i++){
                opencv_abrir_imagenes(config);
                MEDIR_TIEMPO_START(start);
                aplicador(config);
                MEDIR_TIEMPO_START(end);
                opencv_liberar_imagenes(config);
                imprimir_tiempos_ejecucion(start, end,0);
        }
}
\end{verbatim}
\end{codesnippet}
La macro MEDIR_TIEMPO_START devuelve en las variables \textit{start} y \textit{end} la cantidad de ciclos de máquina empleados hasta el momento previo y posterior de la ejecuci{on del filtro.
Luego la función imprimir_tiempos_ejecución realiza la resta $end - start$, e imprime este valor en un archivo de texto.
Es necesario mencionar que el tiempo de ejecución de un programa no es siempre el mismo, es decir, si se lo ejecuta sucesivas veces, se obtendrán distinas mediciones.
Esto se debe a que el procesador se encuentra ejecutando otras tareas al momento de ejecución del programa, y la cantidad de tareas ejecutadas es variable, pudiendo generar un error importante en la medición. Por ello ejecutamos cada versión del filtro 99 veces, obteniendo esa cantidad de resultados. %Entonces
A continuación analizaremos los resultados obtenidos.%, pero primero consideramos necesario aclarar que, como en general los resultados se encuentran en el orden de las unidades de millón,
%se modificó el código de la función imprimir_tiempos_ejecucion para que los resultados obtenidos fueran de tipo punto flotante de doble precisión, para así poderlos dividir por 1 millón.%realizamos el experimento de la siguiente forma: resujimos al mínimo la cantidad de tareas del procesador, para así poder obtener buenas mediciones, ejecutamos cada versión del filtro 100 veces, obteniendo esa cantidad de resultados, con el fin de luego poder descartar los {\textit outliers} (valores atípicos)
%en caso que existieran, mediante el cálculo de la mediana.
%\begin{codesnippet}
%\begin{verbatim}
%void imprimir_tiempos_ejecucion(double start, double end, int cant_iteraciones) {
%	double cant_ciclos = (end-start)/1000000;
%
%	FILE* file;
%	file = fopen("./experimentos/tiempos_tiles", "a");
%	fprintf(file,"%.1f\n", cant_ciclos);
%}
%\end{verbatim}
%\end{codesnippet}
\section{Conclusiones y trabajo futuro}


\section{Anexo: Enunciado} 
\input{enunciado}

\end{document}

